SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Strip packing problem</title>

</head>

Strip packing problem

</h1>

</header>

The strip packing problem is a 2-dimensional geometric minimization problem.

Given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip, minimizing its height.

This problem is a cutting and packing problem and is classified as an Open Dimension Problem according to Wäscher et al.<a href="#cite_note-1">[1]</a>

This problem arises in the area of scheduling, where it models jobs that require a contiguous portion of the memory over a given time period. Another example is the area of industrial manufacturing, where rectangular pieces need to be cut out of a sheet of material (e.g., cloth or paper) that has a fixed width but infinite length, and one wants to minimize the wasted material.

This problem was first studied in 1980.<a href="#cite_note-Baker1980-2">[2]</a> It is strongly-NP hard and there exists no polynomial-time approximation algorithm with a ratio smaller than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3/2}</annotation>

</semantics>

</math><img src="./9a94d2d02968e6cbbc338b54f7762ccd20d74805.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 3/2}" loading="lazy"> unless <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=NP}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=NP}</annotation>

</semantics>

</math><img src="./04c4c7e4303f3c01c40c865c6a1a09c4632bb7e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.653ex; height:2.176ex;" alt="{\displaystyle P=NP}" loading="lazy">. However, the best approximation ratio achieved so far (by a polynomial time algorithm by Harren et al.<a href="#cite_note-Harren-3">[3]</a>) is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (5/3+\varepsilon )}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (5/3+\varepsilon )}</annotation>

</semantics>

</math><img src="./0307f080aab5ee1d090eb311b988c8a482f565c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.221ex; height:2.843ex;" alt="{\displaystyle (5/3+\varepsilon )}" loading="lazy">, imposing an open question of whether there is an algorithm with approximation ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3/2}</annotation>

</semantics>

</math><img src="./9a94d2d02968e6cbbc338b54f7762ccd20d74805.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 3/2}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

An instance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I=({\mathcal {I}},W)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I=({\mathcal {I}},W)}</annotation>

</semantics>

</math><img src="./3d8e5005ff6e1a95e64bbd8ded188b730c310b25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.041ex; height:2.843ex;" alt="{\displaystyle I=({\mathcal {I}},W)}" loading="lazy"> of the strip packing problem consists of a strip with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W=1}</annotation>

</semantics>

</math><img src="./afc347a1c1682ec642190f936d6b859e43746c30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.696ex; height:2.176ex;" alt="{\displaystyle W=1}" loading="lazy"> and infinite height, as well as a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> of rectangular items.

Each item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy"> has a width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}\in (0,1]\cap \mathbb {Q} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{i}\in (0,1]\cap \mathbb {Q} }</annotation>

</semantics>

</math><img src="./b34801711210d06c271bc77f401695f58d56b351.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.606ex; height:2.843ex;" alt="{\displaystyle w_{i}\in (0,1]\cap \mathbb {Q} }" loading="lazy"> and a height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{i}\in (0,1]\cap \mathbb {Q} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{i}\in (0,1]\cap \mathbb {Q} }</annotation>

</semantics>

</math><img src="./ba0d6b550793af71aaf38d2d7e705c863625d569.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.28ex; height:2.843ex;" alt="{\displaystyle h_{i}\in (0,1]\cap \mathbb {Q} }" loading="lazy">.

A packing of the items is a mapping that maps each lower-left corner of an item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy"> to a position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{i},y_{i})\in ([0,1-w_{i}]\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{i},y_{i})\in ([0,1-w_{i}]\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}}</annotation>

</semantics>

</math><img src="./0422f29fff6bc33461aed836e4851a301c8286f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:32.89ex; height:3.009ex;" alt="{\displaystyle (x_{i},y_{i})\in ([0,1-w_{i}]\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}}" loading="lazy"> inside the strip.

An inner point of a placed item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy"> is a point from the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {inn} (i)=\{(x,y)\in \mathbb {Q} \times \mathbb {Q} |x_{i}<x<x_{i}+w_{i},y_{i}<y<y_{i}+h_{i}\}}">

</mrow>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {inn} (i)=\{(x,y)\in \mathbb {Q} \times \mathbb {Q} |x_{i}<x<x_{i}+w_{i},y_{i}<y<y_{i}+h_{i}\}}</annotation>

</semantics>

</math><img src="./f792e48c1c504020cf7b459439da0e7fe05f97f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:60.872ex; height:2.843ex;" alt="{\displaystyle \mathrm {inn} (i)=\{(x,y)\in \mathbb {Q} \times \mathbb {Q} |x_{i}<x<x_{i}+w_{i},y_{i}<y<y_{i}+h_{i}\}}" loading="lazy">.

Two (placed) items overlap if they share an inner point.

The height of the packing is defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}}</annotation>

</semantics>

</math><img src="./38a0b1c4682e153a11e60be2a45f7f78095999c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.351ex; height:2.843ex;" alt="{\displaystyle \max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}}" loading="lazy">.

The objective is to find an overlapping-free packing of the items inside the strip while minimizing the height of the packing.

This definition is used for all polynomial time algorithms. For <a href="Pseudo-polynomial_time" title="Pseudo-polynomial time">pseudo-polynomial time</a> and <a href="Parameterized_complexity" title="Parameterized complexity">FPT</a>-algorithms, the definition is slightly changed for the simplification of notation. In this case, all appearing sizes are integral. Especially the width of the strip is given by an arbitrary integer number larger than 1. Note that these two definitions are equivalent.

<div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2></div>

There are several variants of the strip packing problem that have been studied. These variants concern the objects' geometry, the problem's dimension, the rotateability of the items, and the structure of the packing.<a href="#cite_note-4">[4]</a>

Geometry: In the standard variant of this problem, the set of given items consists of rectangles.

In an often considered subcase, all the items have to be squares. This variant was already considered in the first paper about strip packing.<a href="#cite_note-Baker1980-2">[2]</a>

Additionally, variants where the shapes are circular or even irregular have been studied. In the latter case, it is referred to as irregular strip packing.

Dimension:

When not mentioned differently, the strip packing problem is a 2-dimensional problem. However, it also has been studied in three or even more dimensions. In this case, the objects are <a href="Hyperrectangles" class="mw-redirect" title="Hyperrectangles">hyperrectangles</a>, and the strip is open-ended in one dimension and bounded in the residual ones.

Rotation: In the classical strip packing problem, the items are not allowed to be rotated. However, variants have been studied where rotating by 90 degrees or even an arbitrary angle is allowed.

Structure:

In the general strip packing problem, the structure of the packing is irrelevant.

However, there are applications that have explicit requirements on the structure of the packing. One of these requirements is to be able to cut the items from the strip by horizontal or vertical edge-to-edge cuts.

Packings that allow this kind of cutting are called <a href="Guillotine_problem" class="mw-redirect" title="Guillotine problem">guillotine packing</a>.

<div class="mw-heading mw-heading2"><h2 id="Hardness">Hardness</h2></div>

The strip packing problem contains the <a href="Bin_packing_problem" title="Bin packing problem">bin packing problem</a> as a special case when all the items have the same height 1.

For this reason, it is strongly NP-hard, and there can be no polynomial time <a href="Approximation_algorithm" title="Approximation algorithm">approximation algorithm</a> that has an approximation ratio smaller than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3/2}</annotation>

</semantics>

</math><img src="./9a94d2d02968e6cbbc338b54f7762ccd20d74805.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 3/2}" loading="lazy"> unless <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=NP}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=NP}</annotation>

</semantics>

</math><img src="./04c4c7e4303f3c01c40c865c6a1a09c4632bb7e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.653ex; height:2.176ex;" alt="{\displaystyle P=NP}" loading="lazy">.

Furthermore, unless <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=NP}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=NP}</annotation>

</semantics>

</math><img src="./04c4c7e4303f3c01c40c865c6a1a09c4632bb7e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.653ex; height:2.176ex;" alt="{\displaystyle P=NP}" loading="lazy">, there cannot be a <a href="Pseudo-polynomial_time" title="Pseudo-polynomial time">pseudo-polynomial time</a> algorithm that has an approximation ratio smaller than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 5/4}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 5/4}</annotation>

</semantics>

</math><img src="./63219705fde91ebcc4014679ab352a935bb17990.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 5/4}" loading="lazy">,<a href="#cite_note-Henning-5">[5]</a> which can be proven by a reduction from the <a href="Strongly_NP-complete" class="mw-redirect" title="Strongly NP-complete">strongly NP-complete</a> <a href="3-partition_problem" title="3-partition problem">3-partition problem</a>.

Note that both lower bounds <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3/2}</annotation>

</semantics>

</math><img src="./9a94d2d02968e6cbbc338b54f7762ccd20d74805.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 3/2}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 5/4}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 5/4}</annotation>

</semantics>

</math><img src="./63219705fde91ebcc4014679ab352a935bb17990.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 5/4}" loading="lazy"> also hold for the case that a rotation of the items by 90 degrees is allowed.

Additionally, it was proven by Ashok et al.<a href="#cite_note-6">[6]</a> that strip packing is <a href="Parameterized_complexity" title="Parameterized complexity"> W[1]-hard</a> when parameterized by the height of the optimal packing.

<div class="mw-heading mw-heading2"><h2 id="Properties_of_optimal_solutions">Properties of optimal solutions</h2></div>

There are two trivial lower bounds on optimal solutions.

The first is the height of the largest item.

Define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }(I):=\max\{h(i)|i\in {\mathcal {I}}\}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }(I):=\max\{h(i)|i\in {\mathcal {I}}\}}</annotation>

</semantics>

</math><img src="./2322bf8270448ec0760e819b9a2fa0d49f090eb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.74ex; height:2.843ex;" alt="{\displaystyle h_{\max }(I):=\max\{h(i)|i\in {\mathcal {I}}\}}" loading="lazy">.

Then it holds that

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(I)\geq h_{\max }(I)}</annotation>

</semantics>

</math><img src="./61be06a09e483696ac413520387f14791d3a0f0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.846ex; height:2.843ex;" alt="{\displaystyle OPT(I)\geq h_{\max }(I)}" loading="lazy">.

Another lower bound is given by the total area of the items.

Define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)}">

</mrow>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)}</annotation>

</semantics>

</math><img src="./e93a20d012f3a88352cc100f5c57dc15fac4b4c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:25.795ex; height:5.676ex;" alt="{\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)}" loading="lazy"> then it holds that

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(I)\geq \mathrm {AREA} ({\mathcal {I}})/W}</annotation>

</semantics>

</math><img src="./0cd50e04c9e748f6d239e1bda309b2e9cc010792.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.913ex; height:2.843ex;" alt="{\displaystyle OPT(I)\geq \mathrm {AREA} ({\mathcal {I}})/W}" loading="lazy">.

The following two lower bounds take notice of the fact that certain items cannot be placed next to each other in the strip, and can be computed in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log(n))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log(n))}</annotation>

</semantics>

</math><img src="./75ac2d2b1318fe271226ab13f0eb6c0129df930f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.617ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log(n))}" loading="lazy">.<a href="#cite_note-MartelloExact-7">[7]</a>

For the first lower bound assume that the items are sorted by non-increasing height. Define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}}">

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}}</annotation>

</semantics>

</math><img src="./6fcecee8cfadbf4d3c870e2f3501187371b89d02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:28.054ex; height:7.676ex;" alt="{\displaystyle k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}}" loading="lazy">. For each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l>k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l>k}</annotation>

</semantics>

</math><img src="./688c6a57b28eb2e1fdcb26077b751a3f07eb95d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.003ex; height:2.176ex;" alt="{\displaystyle l>k}" loading="lazy"> define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i(l)\leq k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i(l)\leq k}</annotation>

</semantics>

</math><img src="./f852e256120906610c7fe81c7bc723509f9f3349.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.615ex; height:2.843ex;" alt="{\displaystyle i(l)\leq k}" loading="lazy"> the first index such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(l)+\sum _{j=1}^{i(l)}w(j)>W}">

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(l)+\sum _{j=1}^{i(l)}w(j)>W}</annotation>

</semantics>

</math><img src="./704220285cba1991e060e21d5c1136e9266dc2a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:20.714ex; height:8.009ex;" alt="{\displaystyle w(l)+\sum _{j=1}^{i(l)}w(j)>W}" loading="lazy">. Then it holds that

<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle OPT(I)\geq \max\{h(l)+h(i(l))|l>k\wedge w(l)+\sum _{j=1}^{i(l)}w(j)>W\}}">

</mrow>

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(I)\geq \max\{h(l)+h(i(l))|l>k\wedge w(l)+\sum _{j=1}^{i(l)}w(j)>W\}}</annotation>

</semantics>

</math><img src="./e2013d4aab1e91041ba27e25987a58347efdc438.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:59.967ex; height:8.009ex;" alt="{\displaystyle OPT(I)\geq \max\{h(l)+h(i(l))|l>k\wedge w(l)+\sum _{j=1}^{i(l)}w(j)>W\}}" loading="lazy">.<a href="#cite_note-MartelloExact-7">[7]</a>

For the second lower bound, partition the set of items into three sets. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha \in [1,W/2]\cap \mathbb {N} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha \in [1,W/2]\cap \mathbb {N} }</annotation>

</semantics>

</math><img src="./0274c4c635ab15dcd8078105757ce279f860e1b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.839ex; height:2.843ex;" alt="{\displaystyle \alpha \in [1,W/2]\cap \mathbb {N} }" loading="lazy"> and define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}}</annotation>

</semantics>

</math><img src="./f80e31b7b8b5a12205ddcaeefbe876cf4f16a9df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.069ex; width:31.677ex; height:2.843ex;" alt="{\displaystyle {\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}}</annotation>

</semantics>

</math><img src="./c86d07bd979e35a68ca1452062db4ecf74b11262.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.069ex; width:39.535ex; height:2.843ex;" alt="{\displaystyle {\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}}</annotation>

</semantics>

</math><img src="./4964f3dbfa20933d077e42fe2b3e956c7acfd3dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.069ex; width:34.26ex; height:2.843ex;" alt="{\displaystyle {\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}}" loading="lazy">. Then it holds that

</mrow>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</munder>

<msub>

<mrow>

<mfrac>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

</munder>

</mfrac>

</mrow>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(I)\geq \max _{\alpha \in [1,W/2]\cap \mathbb {N} }{\Bigg \{}\sum _{i\in {\mathcal {I}}_{1}(\alpha )\cup {\mathcal {I}}_{2}(\alpha )}h(i)+\left({\frac {\sum _{i\in {\mathcal {I}}_{3}(\alpha )h(i)w(i)-\sum _{i\in {\mathcal {I}}_{2}(\alpha )}(W-w(i))h(i)}}{W}}\right)_{+}{\Bigg \}}}</annotation>

</semantics>

</math><img src="./1d9a7e4188df7419d989cdcc46686b8918b075e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:82.487ex; height:8.676ex;" alt="{\displaystyle OPT(I)\geq \max _{\alpha \in [1,W/2]\cap \mathbb {N} }{\Bigg \{}\sum _{i\in {\mathcal {I}}_{1}(\alpha )\cup {\mathcal {I}}_{2}(\alpha )}h(i)+\left({\frac {\sum _{i\in {\mathcal {I}}_{3}(\alpha )h(i)w(i)-\sum _{i\in {\mathcal {I}}_{2}(\alpha )}(W-w(i))h(i)}}{W}}\right)_{+}{\Bigg \}}}" loading="lazy">,<a href="#cite_note-MartelloExact-7">[7]</a> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x)_{+}:=\max\{x,0\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x)_{+}:=\max\{x,0\}}</annotation>

</semantics>

</math><img src="./145d7f70798f5ffec683dd150c6139720cb801b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.572ex; height:2.843ex;" alt="{\displaystyle (x)_{+}:=\max\{x,0\}}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {R} }</annotation>

</semantics>

</math><img src="./a9c6d458566aec47a7259762034790c8981aefab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.848ex; height:2.176ex;" alt="{\displaystyle x\in \mathbb {R} }" loading="lazy">.

On the other hand, Steinberg<a href="#cite_note-Steinberg-8">[8]</a> has shown that the height of an optimal solution can be upper bounded by

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(I)\leq 2\max\{h_{\max }(I),\mathrm {AREA} ({\mathcal {I}})/W\}.}</annotation>

</semantics>

</math><img src="./b4501d8698d74f4fbb4e928a1913db736d78540d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.406ex; height:2.843ex;" alt="{\displaystyle OPT(I)\leq 2\max\{h_{\max }(I),\mathrm {AREA} ({\mathcal {I}})/W\}.}" loading="lazy">

More precisely he showed that given a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W\geq w_{\max }({\mathcal {I}})}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W\geq w_{\max }({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./0738c29204a5d07124c6283d22e8ed9ff474acd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.79ex; height:2.843ex;" alt="{\displaystyle W\geq w_{\max }({\mathcal {I}})}" loading="lazy"> and a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H\geq h_{\max }(I)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H\geq h_{\max }(I)}</annotation>

</semantics>

</math><img src="./c0245dbd55db38be29f1b7a54ff32529dfbe8b4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.773ex; height:2.843ex;" alt="{\displaystyle H\geq h_{\max }(I)}" loading="lazy"> then the items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> can be placed inside a box with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"> and height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> if

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle WH\geq 2\mathrm {AREA} ({\mathcal {I}})+(2w_{\max }({\mathcal {I}})-W)_{+}(2h_{\max }(I)-H)_{+}}</annotation>

</semantics>

</math><img src="./ccd5eeee6f57b27c3371251638a9342f3c5b87f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:56.694ex; height:2.843ex;" alt="{\displaystyle WH\geq 2\mathrm {AREA} ({\mathcal {I}})+(2w_{\max }({\mathcal {I}})-W)_{+}(2h_{\max }(I)-H)_{+}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x)_{+}:=\max\{x,0\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x)_{+}:=\max\{x,0\}}</annotation>

</semantics>

</math><img src="./145d7f70798f5ffec683dd150c6139720cb801b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.572ex; height:2.843ex;" alt="{\displaystyle (x)_{+}:=\max\{x,0\}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Polynomial_time_approximation_algorithms">Polynomial time approximation algorithms</h2></div>

Since this problem is NP-hard, <a href="Approximation_algorithms" class="mw-redirect" title="Approximation algorithms">approximation algorithms</a> have been studied for this problem.

Most of the <a href="Heuristic_(computer_science)" title="Heuristic (computer science)">heuristic approaches</a> have an approximation ratio between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3}</annotation>

</semantics>

</math><img src="./991e33c6e207b12546f15bdfee8b5726eafbbb2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 3}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy">.

Finding an algorithm with a ratio below <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy"> seems complicated, and

the complexity of the corresponding algorithms increases regarding their running time and their descriptions.

The smallest approximation ratio achieved so far is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (5/3+\varepsilon )}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (5/3+\varepsilon )}</annotation>

</semantics>

</math><img src="./0307f080aab5ee1d090eb311b988c8a482f565c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.221ex; height:2.843ex;" alt="{\displaystyle (5/3+\varepsilon )}" loading="lazy">.

<caption>Overview of polynomial time approximations

</caption>

<th>Approximation guarantee</th>

<th>Source

</th></tr>

<tr>

<td>Bottom-Up Left-Justified (BL)</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3OPT(I)}</annotation>

</semantics>

</math><img src="./09b7934932bb917df9d050e23f19676d832cf521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.298ex; height:2.843ex;" alt="{\displaystyle 3OPT(I)}" loading="lazy"></td>

<td>Baker et al.<a href="#cite_note-Baker1980-2">[2]</a>

</td></tr>

<tr>

<td rowspan="3">1980

</td>

<td>Next-Fit Decreasing-Height (NFDH)

</td>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2OPT(I)+h_{\max }(I)\leq 3OPT(I)}</annotation>

</semantics>

</math><img src="./20b90d4db42ad922d9a7bf46d9018ea2b23aa8b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.147ex; height:2.843ex;" alt="{\displaystyle 2OPT(I)+h_{\max }(I)\leq 3OPT(I)}" loading="lazy">

</td>

<td rowspan="3">Coffman et al.<a href="#cite_note-Coffman1980-9">[9]</a>

</td></tr>

<tr>

<td>First-Fit Decreasing-Height (FFDH)

</td>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1.7OPT(I)+h_{\max }(I)\leq 2.7OPT(I)}</annotation>

</semantics>

</math><img src="./c445feb8d68e3a5ce75e5ad08356af6cdec09296.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.766ex; height:2.843ex;" alt="{\displaystyle 1.7OPT(I)+h_{\max }(I)\leq 2.7OPT(I)}" loading="lazy">

</td></tr>

<tr>

<td>Split-Fit (SF)

</td>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1.5OPT(I)+2h_{\max }(I)}</annotation>

</semantics>

</math><img src="./a19aa9208b02c202d20a2e54e25765debd0c0f72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.722ex; height:2.843ex;" alt="{\displaystyle 1.5OPT(I)+2h_{\max }(I)}" loading="lazy">

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2OPT(I)+h_{\max }(I)/2\leq 2.5OPT(I)}</annotation>

</semantics>

</math><img src="./f141dd272cc867eb0d7c38501b56ab604b0c5f63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.281ex; height:2.843ex;" alt="{\displaystyle 2OPT(I)+h_{\max }(I)/2\leq 2.5OPT(I)}" loading="lazy"></td>

<td>Sleator<a href="#cite_note-Sleator-10">[10]</a>

</td></tr>

<tr>

<td rowspan="2">1981

</td>

<td>Split Algorithm (SP)

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3OPT(I)}</annotation>

</semantics>

</math><img src="./09b7934932bb917df9d050e23f19676d832cf521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.298ex; height:2.843ex;" alt="{\displaystyle 3OPT(I)}" loading="lazy">

</td>

<td rowspan="2">Golan<a href="#cite_note-Golan-11">[11]</a>

</td></tr>

<tr>

<td>Mixed Algoritghm

</td>

</mrow>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (4/3)OPT(I)+7{\frac {1}{18}}h_{\max }(I)}</annotation>

</semantics>

</math><img src="./4c81577ede7530b3f2ed7e308ecd10bbc0734b58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:28.208ex; height:5.176ex;" alt="{\displaystyle (4/3)OPT(I)+7{\frac {1}{18}}h_{\max }(I)}" loading="lazy">

</td></tr>

<tr>

</mrow>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (5/4)OPT(I)+6{\frac {7}{8}}h_{\max }(I)}</annotation>

</semantics>

</math><img src="./cbfff8d85c6ff72a6c48258f3a340d58d8580c7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:27.045ex; height:5.176ex;" alt="{\displaystyle (5/4)OPT(I)+6{\frac {7}{8}}h_{\max }(I)}" loading="lazy"></td>

<td>Baker et al.<a href="#cite_note-12">[12]</a>

</td></tr>

<tr>

<td>Reverse-Fit</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2OPT(I)}</annotation>

</semantics>

</math><img src="./3c91dce304fdeaa0dad68c8403ed608a0fdc3436.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.298ex; height:2.843ex;" alt="{\displaystyle 2OPT(I)}" loading="lazy"></td>

<td>Schiermeyer<a href="#cite_note-Schiermeyer-13">[13]</a>

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2OPT(I)}</annotation>

</semantics>

</math><img src="./3c91dce304fdeaa0dad68c8403ed608a0fdc3436.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.298ex; height:2.843ex;" alt="{\displaystyle 2OPT(I)}" loading="lazy"></td>

<td>Steinberg<a href="#cite_note-Steinberg-8">[8]</a>

</td></tr>

<tr>

<td>2000

</td>

<td>

</td>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(1/\varepsilon ^{2})h_{\max }(I)}</annotation>

</semantics>

</math><img src="./68d201df1db63ff5d6c48d0589e79237ee140b34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.605ex; height:3.176ex;" alt="{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(1/\varepsilon ^{2})h_{\max }(I)}" loading="lazy">

</td>

<td>Kenyon, Rémila<a href="#cite_note-KenyonRémila-14">[14]</a>

</td></tr>

<tr>

<td>2009

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1.9396OPT(I)}</annotation>

</semantics>

</math><img src="./6668111479c179ee0fcbc2149dc07271a7dae19c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.595ex; height:2.843ex;" alt="{\displaystyle 1.9396OPT(I)}" loading="lazy">

</td>

<td>Harren, van Stee<a href="#cite_note-15">[15]</a>

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1+\varepsilon )OPT(I)+h_{\max }(I)}</annotation>

</semantics>

</math><img src="./0f278e8325fab15294dcb3727bf33d098ec67b3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.483ex; height:2.843ex;" alt="{\displaystyle (1+\varepsilon )OPT(I)+h_{\max }(I)}" loading="lazy"></td>

<td>Jansen, Solis-Oba<a href="#cite_note-16">[16]</a>

</td></tr>

<tr>

<td>2011

</td>

<td>

</td>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)}</annotation>

</semantics>

</math><img src="./1ea2772573e56c73ae9bc3ccace69ad886eb0d2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:39.578ex; height:2.843ex;" alt="{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)}" loading="lazy">

</td>

<td>Bougeret et al.<a href="#cite_note-17">[17]</a>

</td></tr>

<tr>

<td>2012

</td>

<td>

</td>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)}</annotation>

</semantics>

</math><img src="./1ea2772573e56c73ae9bc3ccace69ad886eb0d2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:39.578ex; height:2.843ex;" alt="{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)}" loading="lazy">

</td>

<td>Sviridenko<a href="#cite_note-18">[18]</a>

</td></tr>

<tr>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (5/3+\varepsilon )OPT(I)}</annotation>

</semantics>

</math><img src="./11e0ddf1d9c6d0c7d6de17c5d12b07c0d3d5d627.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.357ex; height:2.843ex;" alt="{\displaystyle (5/3+\varepsilon )OPT(I)}" loading="lazy"></td>

<td>Harren et al.<a href="#cite_note-Harren-3">[3]</a>

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Bottom-up_left-justified_(BL)">Bottom-up left-justified (BL)</h3></div>

This algorithm was first described by Baker et al.<a href="#cite_note-Baker1980-2">[2]</a> It works as follows:

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> be a sequence of rectangular items.

The algorithm iterates the sequence in the given order.

For each considered item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\in L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\in L}</annotation>

</semantics>

</math><img src="./11a98a1cc86b8ef2b610595fd5a5cdf4480c592e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle r\in L}" loading="lazy">, it searches for the bottom-most position to place it and then shifts it as far to the left as possible.

Hence, it places <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> at the bottom-most left-most possible coordinate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,y)}</annotation>

</semantics>

</math><img src="./41cf50e4a314ca8e2c30964baa8d26e5be7a9386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.328ex; height:2.843ex;" alt="{\displaystyle (x,y)}" loading="lazy"> in the strip.

This algorithm has the following properties:

<ul><li>The approximation ratio of this algorithm cannot be bounded by a constant. More precisely they showed that for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M>0}</annotation>

</semantics>

</math><img src="./a7f423ab77b3411ec2803520a07c0dfae6ceb826.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.703ex; height:2.176ex;" alt="{\displaystyle M>0}" loading="lazy"> there exists a list <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> of rectangular items ordered by increasing width such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BL(L)/OPT(L)>M}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BL(L)/OPT(L)>M}</annotation>

</semantics>

</math><img src="./5525a9c2366bf0e8a45de74e223a76b462c5d5c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.989ex; height:2.843ex;" alt="{\displaystyle BL(L)/OPT(L)>M}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BL(L)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BL(L)}</annotation>

</semantics>

</math><img src="./7f3da0523e3e641bd6933a0383bc72ed67f1e21a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.739ex; height:2.843ex;" alt="{\displaystyle BL(L)}" loading="lazy"> is the height of the packing created by the BL algorithm and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle OPT(L)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(L)}</annotation>

</semantics>

</math><img src="./8bdf6a3862863682a23a12cb43073b8da2aed830.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.547ex; height:2.843ex;" alt="{\displaystyle OPT(L)}" loading="lazy"> is the height of the optimal solution for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy">.<a href="#cite_note-Baker1980-2">[2]</a></li>

<li>If the items are ordered by decreasing widths, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BL(L)/OPT(L)\leq 3}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BL(L)/OPT(L)\leq 3}</annotation>

</semantics>

</math><img src="./00f4996da825936337953ea4a5a86c0633684ea1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.709ex; height:2.843ex;" alt="{\displaystyle BL(L)/OPT(L)\leq 3}" loading="lazy">.<a href="#cite_note-Baker1980-2">[2]</a></li>

<li>If the item are all squares and are ordered by decreasing widths, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BL(L)/OPT(L)\leq 2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BL(L)/OPT(L)\leq 2}</annotation>

</semantics>

</math><img src="./927e793c263ad1205dd00fcecfcaf1ec075cff5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.709ex; height:2.843ex;" alt="{\displaystyle BL(L)/OPT(L)\leq 2}" loading="lazy">.<a href="#cite_note-Baker1980-2">[2]</a></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta >0}</annotation>

</semantics>

</math><img src="./595d5cea06fdcaf2642caf549eda2cfc537958a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.343ex;" alt="{\displaystyle \delta >0}" loading="lazy">, there exists a list <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> of rectangles ordered by decreasing widths such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BL(L)/OPT(L)>3-\delta }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BL(L)/OPT(L)>3-\delta }</annotation>

</semantics>

</math><img src="./e1338100319064f86f83627c4aefe60063ddf416.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.599ex; height:2.843ex;" alt="{\displaystyle BL(L)/OPT(L)>3-\delta }" loading="lazy">.<a href="#cite_note-Baker1980-2">[2]</a></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta >0}</annotation>

</semantics>

</math><img src="./595d5cea06fdcaf2642caf549eda2cfc537958a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.343ex;" alt="{\displaystyle \delta >0}" loading="lazy">, there exists a list <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> of squares ordered by decreasing widths such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BL(L)/OPT(L)>2-\delta }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BL(L)/OPT(L)>2-\delta }</annotation>

</semantics>

</math><img src="./4caaf302b614ed9172eeb7dcb43f6d9a0b84e55a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.599ex; height:2.843ex;" alt="{\displaystyle BL(L)/OPT(L)>2-\delta }" loading="lazy">.<a href="#cite_note-Baker1980-2">[2]</a></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon \in (0,1]}</annotation>

</semantics>

</math><img src="./eb28b09204fc15408327090379ae3aeb11572732.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.834ex; height:2.843ex;" alt="{\displaystyle \varepsilon \in (0,1]}" loading="lazy">, there exists an instance containing only squares where each order of the squares <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> has a ratio of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}}">

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}}</annotation>

</semantics>

</math><img src="./833cb3e75ef458f9f0ed8848d23def96d7c8479e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:26.632ex; height:5.343ex;" alt="{\displaystyle BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}}" loading="lazy">, i.e., there exist instances where BL does not find the optimum even when iterating all possible orders of the items.<a href="#cite_note-Baker1980-2">[2]</a> In 2024 this lower bound has been improved by Hougardy and Zondervan to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}}">

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}}</annotation>

</semantics>

</math><img src="./bb13654a549eab56e1335cb076dd607763df981c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:25.47ex; height:5.343ex;" alt="{\displaystyle BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}}" loading="lazy">.<a href="#cite_note-19">[19]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Next-fit_decreasing-height_(NFDH)">Next-fit decreasing-height (NFDH)</h3></div>

This algorithm was first described by Coffman et al.<a href="#cite_note-Coffman1980-9">[9]</a> in 1980 and works as follows:

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> be the given set of rectangular items.

First, the algorithm sorts the items by order of nonincreasing height.

Then, starting at position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (0,0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (0,0)}</annotation>

</semantics>

</math><img src="./5d630d3e781a53b0a3559ae7e5b45f9479a3141a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (0,0)}" loading="lazy">, the algorithm places the items next to each other in the strip until the next item will overlap the right border of the strip.

At this point, the algorithm defines a new level at the top of the tallest item in the current level and places the items next to each other in this new level.

This algorithm has the following properties:

<ul><li>The running time can be bounded by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}</annotation>

</semantics>

</math><img src="./1e215f5bc0c0c7803eae6ab18b6b936c951d951c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.399ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}" loading="lazy"> and if the items are already sorted even by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}</annotation>

</semantics>

</math><img src="./db598ecc7912b7c0f319c50a13231c4e0a2a2f50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.445ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}" loading="lazy">.</li>

<li>For every set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">, it produces a packing of height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}">

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./5c8f25cbcb4568d056d17ee1c119a87d091275b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.999ex; height:2.843ex;" alt="{\displaystyle NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }}</annotation>

</semantics>

</math><img src="./7c60f7eccb49f128aa8a7d3a4e8835cd7484d271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.63ex; height:2.509ex;" alt="{\displaystyle h_{\max }}" loading="lazy"> is the largest height of an item in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">.<a href="#cite_note-Coffman1980-9">[9]</a></li>

<li>For every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy"> there exists a set of rectangles <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).}</annotation>

</semantics>

</math><img src="./270c7da3a3332f43d9afbcb9128a981e0f10fa1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.838ex; height:2.843ex;" alt="{\displaystyle NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).}" loading="lazy"><a href="#cite_note-Coffman1980-9">[9]</a></li>

<li>The packing generated is a guillotine packing. This means the items can be obtained through a sequence of horizontal or vertical edge-to-edge cuts.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="First-fit_decreasing-height_(FFDH)">First-fit decreasing-height (FFDH)</h3></div>

This algorithm, first described by Coffman et al.<a href="#cite_note-Coffman1980-9">[9]</a> in 1980, works similar to the NFDH algorithm.

However, when placing the next item, the algorithm scans the levels from bottom to top and places the item in the first level on which it will fit.

A new level is only opened if the item does not fit in any previous ones.

This algorithm has the following properties:

<ul><li>The running time can be bounded by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}</annotation>

</semantics>

</math><img src="./4701bc4ab32ccf79d0e6703e20d157dcde274662.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.499ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}" loading="lazy">, since there are at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {I}}|}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {I}}|}</annotation>

</semantics>

</math><img src="./b7843389886f11cd23f247fe9b68ff1d61706cf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.786ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {I}}|}" loading="lazy"> levels.</li>

<li>For every set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> it produces a packing of height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})}">

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./1720d7ee0cc3d534868fb690fa7b11cb845d5557.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.295ex; height:2.843ex;" alt="{\displaystyle FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }}</annotation>

</semantics>

</math><img src="./7c60f7eccb49f128aa8a7d3a4e8835cd7484d271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.63ex; height:2.509ex;" alt="{\displaystyle h_{\max }}" loading="lazy"> is the largest height of an item in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">.<a href="#cite_note-Coffman1980-9">[9]</a></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\geq 2}</annotation>

</semantics>

</math><img src="./eca2e437e89ef4565a87f1a6d90ed37eef1d8ce3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.301ex; height:2.343ex;" alt="{\displaystyle m\geq 2}" loading="lazy">. For any set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> and strip with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i)\leq W/m}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i)\leq W/m}</annotation>

</semantics>

</math><img src="./e6c74189d06a597986ad267314009a35588ba413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.012ex; height:2.843ex;" alt="{\displaystyle w(i)\leq W/m}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy">, it holds that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }}">

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }}</annotation>

</semantics>

</math><img src="./fc079c8e75a5742fc6c0435de9707d43aed15cc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.361ex; height:2.843ex;" alt="{\displaystyle FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }}" loading="lazy">. Furthermore, for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy">, there exists such a set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})}">

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./0d1428798dfb60091eb645cb82e2acbebaeb3a51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.814ex; height:2.843ex;" alt="{\displaystyle FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})}" loading="lazy">.<a href="#cite_note-Coffman1980-9">[9]</a></li>

<li>If all the items in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> are squares, it holds that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }}">

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }}</annotation>

</semantics>

</math><img src="./6950fc141ef6d8833cedb1754964c74f8f919cb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.093ex; height:2.843ex;" alt="{\displaystyle FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }}" loading="lazy">. Furthermore, for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy">, there exists a set of squares <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})}">

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./210b389e9b84e4231d7c6ae6cfbbf46907766b8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.934ex; height:2.843ex;" alt="{\displaystyle FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})}" loading="lazy">.<a href="#cite_note-Coffman1980-9">[9]</a></li>

<li>The packing generated is a guillotine packing. This means the items can be obtained through a sequence of horizontal or vertical edge-to-edge cuts.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="The_split-fit_algorithm_(SF)">The split-fit algorithm (SF)</h3></div>

This algorithm was first described by Coffman et al.<a href="#cite_note-Coffman1980-9">[9]</a>

For a given set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> and strip with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy">, it works as follows:

<ol><li>Determinate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./42411e85d874a733209223302bbd8d5e3ad04cb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.559ex; height:2.176ex;" alt="{\displaystyle m\in \mathbb {N} }" loading="lazy">, the largest integer such that the given rectangles have width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W/m}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W/m}</annotation>

</semantics>

</math><img src="./fd6d278810d3e46867779ab4f2cba3caee24de1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.638ex; height:2.843ex;" alt="{\displaystyle W/m}" loading="lazy"> or less.</li>

<li>Divide <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> into two sets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{wide}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{wide}}</annotation>

</semantics>

</math><img src="./94fa4a3b3383c86eb9d8092146bbdb2fc8be4d02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:4.938ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{wide}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{narrow}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{narrow}}</annotation>

</semantics>

</math><img src="./b7aedb5a40b6bca4fd54fa1f88222251e8ab72d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:6.881ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{narrow}}" loading="lazy">, such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{wide}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{wide}}</annotation>

</semantics>

</math><img src="./94fa4a3b3383c86eb9d8092146bbdb2fc8be4d02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:4.938ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{wide}}" loading="lazy"> contains all the items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy"> with a width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i)>W/(m+1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i)>W/(m+1)}</annotation>

</semantics>

</math><img src="./ed973f41b77ab8107a93a42e55c6367517aba55e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.825ex; height:2.843ex;" alt="{\displaystyle w(i)>W/(m+1)}" loading="lazy"> while <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{narrow}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{narrow}}</annotation>

</semantics>

</math><img src="./b7aedb5a40b6bca4fd54fa1f88222251e8ab72d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:6.881ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{narrow}}" loading="lazy"> contains all the items with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i)\leq W/(m+1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i)\leq W/(m+1)}</annotation>

</semantics>

</math><img src="./c680553bfb3987ab10ceede98047838ecbb45c5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.825ex; height:2.843ex;" alt="{\displaystyle w(i)\leq W/(m+1)}" loading="lazy">.</li>

<li>Order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{wide}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{wide}}</annotation>

</semantics>

</math><img src="./94fa4a3b3383c86eb9d8092146bbdb2fc8be4d02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:4.938ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{wide}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{narrow}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{narrow}}</annotation>

</semantics>

</math><img src="./b7aedb5a40b6bca4fd54fa1f88222251e8ab72d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:6.881ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{narrow}}" loading="lazy"> by nonincreasing height.</li>

<li>Pack the items in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{wide}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{wide}}</annotation>

</semantics>

</math><img src="./94fa4a3b3383c86eb9d8092146bbdb2fc8be4d02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:4.938ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{wide}}" loading="lazy"> with the FFDH algorithm.</li>

<li>Reorder the levels/shelves constructed by FFDH such that all the shelves with a total width larger than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W(m+1)/(m+2)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W(m+1)/(m+2)}</annotation>

</semantics>

</math><img src="./5fd4c1576f3be062aaadcd988eb05db4451e02a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.303ex; height:2.843ex;" alt="{\displaystyle W(m+1)/(m+2)}" loading="lazy"> are below the more narrow ones.</li>

<li>This leaves a rectangular area <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> of with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W/(m+2)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W/(m+2)}</annotation>

</semantics>

</math><img src="./83ede72be16ac3fadac3a1ba18b8b1a846c58774.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.45ex; height:2.843ex;" alt="{\displaystyle W/(m+2)}" loading="lazy">, next to more narrow levels/shelves, that contains no item.</li>

<li>Use the FFDH algorithm to pack the items in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{narrow}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{narrow}}</annotation>

</semantics>

</math><img src="./b7aedb5a40b6bca4fd54fa1f88222251e8ab72d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:6.881ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{narrow}}" loading="lazy"> using the area <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> as well.</li></ol>

This algorithm has the following properties:

<ul><li>For every set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> and the corresponding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">, it holds that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }}">

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }}</annotation>

</semantics>

</math><img src="./3b0fcf5f9c7ac2d91de71ec47824bb3682800520.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:43.597ex; height:2.843ex;" alt="{\displaystyle SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }}" loading="lazy">.<a href="#cite_note-Coffman1980-9">[9]</a> Note that for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=1}</annotation>

</semantics>

</math><img src="./b6100c5ebd48c6fd848709f2be624465203eb173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;" alt="{\displaystyle m=1}" loading="lazy">, it holds that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }}">

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }}</annotation>

</semantics>

</math><img src="./d727da44fc27c321a53d7f5e1bfe6d91f3979d71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.026ex; height:2.843ex;" alt="{\displaystyle SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }}" loading="lazy"></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy">, there is a set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})}">

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./30d371f874ca17593c7b05060483824ac071b381.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.084ex; height:2.843ex;" alt="{\displaystyle SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})}" loading="lazy">.<a href="#cite_note-Coffman1980-9">[9]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Sleator's_algorithm">Sleator's algorithm</h3></div>

For a given set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> and strip with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy">, it works as follows:

<ol><li>Find all the items with a width larger than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W/2}</annotation>

</semantics>

</math><img src="./2246a8ad4758953b9783e7310f002df09bab3388.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.76ex; height:2.843ex;" alt="{\displaystyle W/2}" loading="lazy"> and stack them at the bottom of the strip (in random order). Call the total height of these items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{0}}</annotation>

</semantics>

</math><img src="./08c1c908b03c3f63383c7199465c7fd0b105030f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.393ex; height:2.509ex;" alt="{\displaystyle h_{0}}" loading="lazy">. All the other items will be placed above <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{0}}</annotation>

</semantics>

</math><img src="./08c1c908b03c3f63383c7199465c7fd0b105030f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.393ex; height:2.509ex;" alt="{\displaystyle h_{0}}" loading="lazy">.</li>

<li>Sort all the remaining items in nonincreasing order of height. The items will be placed in this order.</li>

<li>Consider the horizontal line at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{0}}</annotation>

</semantics>

</math><img src="./08c1c908b03c3f63383c7199465c7fd0b105030f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.393ex; height:2.509ex;" alt="{\displaystyle h_{0}}" loading="lazy"> as a shelf. The algorithm places the items on this shelf in nonincreasing order of height until no item is left or the next one does not fit.</li>

<li>Draw a vertical line at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W/2}</annotation>

</semantics>

</math><img src="./2246a8ad4758953b9783e7310f002df09bab3388.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.76ex; height:2.843ex;" alt="{\displaystyle W/2}" loading="lazy">, which cuts the strip into two equal halves.</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{l}}</annotation>

</semantics>

</math><img src="./89eaf90f8ac13f156d1c4fead974e1158d4eee71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.509ex;" alt="{\displaystyle h_{l}}" loading="lazy"> be the highest point covered by any item in the left half and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{r}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{r}}</annotation>

</semantics>

</math><img src="./87b8534147ad8c99d738c25c0ecc134ddef19fd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.313ex; height:2.509ex;" alt="{\displaystyle h_{r}}" loading="lazy"> the corresponding point on the right half. Draw two horizontal line segments of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W/2}</annotation>

</semantics>

</math><img src="./2246a8ad4758953b9783e7310f002df09bab3388.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.76ex; height:2.843ex;" alt="{\displaystyle W/2}" loading="lazy"> at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{l}}</annotation>

</semantics>

</math><img src="./89eaf90f8ac13f156d1c4fead974e1158d4eee71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.509ex;" alt="{\displaystyle h_{l}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{r}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{r}}</annotation>

</semantics>

</math><img src="./87b8534147ad8c99d738c25c0ecc134ddef19fd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.313ex; height:2.509ex;" alt="{\displaystyle h_{r}}" loading="lazy"> across the left and the right half of the strip. These two lines build new shelves on which the algorithm will place the items, as in step 3. Choose the half which has the lower shelf and place the items on this shelf until no other item fits. Repeat this step until no item is left.</li></ol>

This algorithm has the following properties:

<ul><li>The running time can be bounded by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}</annotation>

</semantics>

</math><img src="./1e215f5bc0c0c7803eae6ab18b6b936c951d951c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.399ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}" loading="lazy"> and if the items are already sorted even by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}</annotation>

</semantics>

</math><img src="./db598ecc7912b7c0f319c50a13231c4e0a2a2f50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.445ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}" loading="lazy">.</li>

<li>For every set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> it produces a packing of height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})}">

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./c3b67c6fa46dac36056d43e44a20b84c0d702820.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.084ex; height:2.843ex;" alt="{\displaystyle A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }}</annotation>

</semantics>

</math><img src="./7c60f7eccb49f128aa8a7d3a4e8835cd7484d271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.63ex; height:2.509ex;" alt="{\displaystyle h_{\max }}" loading="lazy"> is the largest height of an item in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">.<a href="#cite_note-Sleator-10">[10]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="The_split_algorithm_(SP)">The split algorithm (SP)</h3></div>

This algorithm is an extension of Sleator's approach and was first described by Golan.<a href="#cite_note-Golan-11">[11]</a>

It places the items in nonincreasing order of width.

The intuitive idea is to split the strip into sub-strips while placing some items.

Whenever possible, the algorithm places the current item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> side-by-side of an already placed item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">.

In this case, it splits the corresponding sub-strip into two pieces: one containing the first item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> and the other containing the current item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">.

If this is not possible, it places <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> on top of an already placed item and does not split the sub-strip.

This algorithm creates a set <samp> S </samp> of sub-strips. For each sub-strip <samp> s ∈ S</samp> we know its lower left corner <samp> s.xposition</samp> and <samp> s.yposition</samp>, its width <samp> s.width</samp>, the horizontal lines parallel to the upper and lower border of the item placed last inside this sub-strip <samp> s.upper</samp> and <samp> s.lower</samp>, as well as the width of it <samp> s.itemWidth</samp>.

<pre>function Split Algorithm (SP) is

input: items <samp>I</samp>, width of the strip <samp>W</samp>

output: A packing of the items

Sort I in nonincreasing order of widths;

Define empty list S of sub-strips;

Define a new sub-strip s with s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W;

Add s to S;

while I not empty do

i := I.pop(); Removes widest item from I

Define new list S_2 containing all the substrips with s.width - s.itemWidth ≥ i.width;

S_2 contains all sub-strips where i fits next to the already placed item

if S_2 is empty then

In this case, place the item on top of another one.

Find the sub-strip s in S with smallest s.upper; i.e. the least filled sub-strip

Place i at position (s.xposition, s.upper);

Update s: s.lower := s.upper; s.upper := s.upper+i.height; s.itemWidth := i.width;

else

In this case, place the item next to another one at the same level and split the corresponding sub-strip at this position.

Find s ∈ S_2 with the smallest s.lower;

Place i at position (s.xposition + s.itemWidth, s.lower);

Remove s from S;

Define two new sub-strips s1 and s2 with

s1.xposition = s.xposition, s1.yposition = s.upper, s1.width = s.itemWidth, s1.lower = s.upper, s1.upper = s.upper, s1.itemWidth = s.itemWidth;

s2.xposition = s.xposition+s.itemWidth, s2.yposition = s.lower, s2.width = s.width - s.itemWidth, s2.lower = s.lower, s2.upper = s.lower + i.height, s2.itemWidth = i.width;

S.add(s1,s2);

return

end function

</pre>

This algorithm has the following properties:

<ul><li>The running time can be bounded by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}</annotation>

</semantics>

</math><img src="./4701bc4ab32ccf79d0e6703e20d157dcde274662.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.499ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}" loading="lazy"> since the number of substrips is bounded by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {I}}|}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {I}}|}</annotation>

</semantics>

</math><img src="./b7843389886f11cd23f247fe9b68ff1d61706cf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.786ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {I}}|}" loading="lazy">.</li>

<li>For any set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> it holds that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}">

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./20018d97d5bd64287d4c1aed6d36fe01583a77ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:39.452ex; height:2.843ex;" alt="{\displaystyle SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}" loading="lazy">.<a href="#cite_note-Golan-11">[11]</a></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy">, there exists a set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./9ec746f172f911b404941d8d036f949f0e1ba702.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.997ex; height:2.843ex;" alt="{\displaystyle SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})}" loading="lazy">.<a href="#cite_note-Golan-11">[11]</a></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C>0}</annotation>

</semantics>

</math><img src="./c84d4126c6df243734f9355927c026df6b0d3859.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.027ex; height:2.176ex;" alt="{\displaystyle C>0}" loading="lazy">, there exists a set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C}</annotation>

</semantics>

</math><img src="./4ce594405f63e4f46b8b5f069742908b1848fa7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.604ex; height:2.843ex;" alt="{\displaystyle SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C}" loading="lazy">.<a href="#cite_note-Golan-11">[11]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Reverse-fit_(RF)">Reverse-fit (RF)</h3></div>

This algorithm was first described by Schiermeyer.<a href="#cite_note-Schiermeyer-13">[13]</a>

The description of this algorithm needs some additional notation.

For a placed item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy">, its lower left corner is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{i},c_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{i},c_{i})}</annotation>

</semantics>

</math><img src="./1281a65bf4beca72fb6b5e1b97b348ccea3bd9a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.679ex; height:2.843ex;" alt="{\displaystyle (a_{i},c_{i})}" loading="lazy"> and its upper right corner by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (b_{i},d_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (b_{i},d_{i})}</annotation>

</semantics>

</math><img src="./5d821d3b67f1c3cfd7d6375dd212920aa0ac25a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.649ex; height:2.843ex;" alt="{\displaystyle (b_{i},d_{i})}" loading="lazy">.

Given a set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> and a strip of width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy">, it works as follows:

<ol><li>Stack all the rectangles of width greater than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W/2}</annotation>

</semantics>

</math><img src="./2246a8ad4758953b9783e7310f002df09bab3388.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.76ex; height:2.843ex;" alt="{\displaystyle W/2}" loading="lazy"> on top of each other (in random order) at the bottom of the strip. Denote by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{0}}</annotation>

</semantics>

</math><img src="./43910602a221b7a4c373791f94793e3008622070.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle H_{0}}" loading="lazy"> the height of this stack. All other items will be packed above <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{0}}</annotation>

</semantics>

</math><img src="./43910602a221b7a4c373791f94793e3008622070.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle H_{0}}" loading="lazy">.</li>

<li>Sort the remaining items in order of nonincreasing height and consider the items in this order in the following steps. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }}</annotation>

</semantics>

</math><img src="./7c60f7eccb49f128aa8a7d3a4e8835cd7484d271.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.63ex; height:2.509ex;" alt="{\displaystyle h_{\max }}" loading="lazy"> be the height of the tallest of these remaining items.</li>

<li>Place the items one by one left aligned on a shelf defined by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{0}}</annotation>

</semantics>

</math><img src="./43910602a221b7a4c373791f94793e3008622070.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle H_{0}}" loading="lazy"> until no other item fit on this shelf or there is no item left. Call this shelf the first level.</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{1}}</annotation>

</semantics>

</math><img src="./14e8880a2e4243a2fe5157e574a0547ef3d5d373.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.393ex; height:2.509ex;" alt="{\displaystyle h_{1}}" loading="lazy"> be the height of the tallest unpacked item. Define a new shelf at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{0}+h_{\max }+h_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{0}+h_{\max }+h_{1}}</annotation>

</semantics>

</math><img src="./d04280cf23da6fb8ae24144ef2958d56aee6a6e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.69ex; height:2.509ex;" alt="{\displaystyle H_{0}+h_{\max }+h_{1}}" loading="lazy">. The algorithm will fill this shelf from right to left, aligning the items to the right, such that the items touch this shelf with their top. Call this shelf the second reverse-level.</li>

<li>Place the items into the two shelves due to First-Fit, i.e., placing the items in the first level where they fit and in the second one otherwise. Proceed until there are no items left, or the total width of the items in the second shelf is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W/2}</annotation>

</semantics>

</math><img src="./2246a8ad4758953b9783e7310f002df09bab3388.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.76ex; height:2.843ex;" alt="{\displaystyle W/2}" loading="lazy">.</li>

<li>Shift the second reverse-level down until an item from it touches an item from the first level. Define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{1}}</annotation>

</semantics>

</math><img src="./4d4d9a872a55b209f2eb7cc23a71e5e1541bd1f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle H_{1}}" loading="lazy"> as the new vertical position of the shifted shelf. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> be the right most pair of touching items with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> placed on the first level and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> on the second reverse-level. Define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{r}:=\max(b_{f},b_{s})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{r}:=\max(b_{f},b_{s})}</annotation>

</semantics>

</math><img src="./686896d3d560bc776cd9441e9e7939a19e5b7d03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.353ex; height:3.009ex;" alt="{\displaystyle x_{r}:=\max(b_{f},b_{s})}" loading="lazy">.</li>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{r}<W/2}</annotation>

</semantics>

</math><img src="./adcd3853ae360d0cdfeefb54d85755fc039ae054.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.162ex; height:2.843ex;" alt="{\displaystyle x_{r}<W/2}" loading="lazy"> then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> is the last rectangle placed in the second reverse-level. Shift all the other items from this level further down (all the same amount) until the first one touches an item from the first level. Again the algorithm determines the rightmost pair of touching items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f'}</annotation>

</semantics>

</math><img src="./258eaada38956fb69b8cb1a2eef46bcb97d3126b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.005ex; height:2.843ex;" alt="{\displaystyle f'}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s'}</annotation>

</semantics>

</math><img src="./5136680c63706cfd17ceddb4acddbfdd0ba5ef2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.775ex; height:2.509ex;" alt="{\displaystyle s'}" loading="lazy">. Define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{2}}</annotation>

</semantics>

</math><img src="./56d2d1733d09f02f33694f72b6da94681021e0f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.393ex; height:2.509ex;" alt="{\displaystyle h_{2}}" loading="lazy"> as the amount by which the shelf was shifted down.

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{2}\leq h(s)}</annotation>

</semantics>

</math><img src="./31bacadd7b6a355eba66926354285893f8e04f08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.73ex; height:2.843ex;" alt="{\displaystyle h_{2}\leq h(s)}" loading="lazy"> then shift <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> to the left until it touches another item or the border of the strip. Define the third level at the top of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s'}</annotation>

</semantics>

</math><img src="./5136680c63706cfd17ceddb4acddbfdd0ba5ef2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.775ex; height:2.509ex;" alt="{\displaystyle s'}" loading="lazy">.</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{2}>h(s)}</annotation>

</semantics>

</math><img src="./070fe9295e9b5673f0d36b8f91aefe9371327480.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.73ex; height:2.843ex;" alt="{\displaystyle h_{2}>h(s)}" loading="lazy"> then shift <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> define the third level at the top of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s'}</annotation>

</semantics>

</math><img src="./5136680c63706cfd17ceddb4acddbfdd0ba5ef2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.775ex; height:2.509ex;" alt="{\displaystyle s'}" loading="lazy">. Place <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> left-aligned in this third level, such that it touches an item from the first level on its left.</li></ol></li>

<li>Continue packing the items using the First-Fit heuristic. Each following level (starting at level three) is defined by a horizontal line through the top of the largest item on the previous level. Note that the first item placed in the next level might not touch the border of the strip with their left side, but an item from the first level or the item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">.</li></ol>

This algorithm has the following properties:

<ul><li>The running time can be bounded by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}</annotation>

</semantics>

</math><img src="./4701bc4ab32ccf79d0e6703e20d157dcde274662.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.499ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}" loading="lazy">, since there are at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {I}}|}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {I}}|}</annotation>

</semantics>

</math><img src="./b7843389886f11cd23f247fe9b68ff1d61706cf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.786ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {I}}|}" loading="lazy"> levels.</li>

<li>For every set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> it produces a packing of height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./3eee574efba3c209cf5bc64851926869f1145d32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.524ex; height:2.843ex;" alt="{\displaystyle RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})}" loading="lazy">.<a href="#cite_note-Schiermeyer-13">[13]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Steinberg's_algorithm_(ST)">Steinberg's algorithm (ST)</h3></div>

Steinbergs algorithm is a recursive one. Given a set of rectangular items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> and a rectangular target region with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"> and height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">, it proposes four reduction rules, that place some of the items and leaves a smaller rectangular region with the same properties as before regarding of the residual items.

Consider the following notations: Given a set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> we denote by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }({\mathcal {I}})}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./0744347543e4b4d18b1e58accf206df98f8982c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.932ex; height:2.843ex;" alt="{\displaystyle h_{\max }({\mathcal {I}})}" loading="lazy"> the tallest item height in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{\max }({\mathcal {I}})}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{\max }({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./84402b78f4fa45f2d0e83f95cf86675ebb31ea24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.257ex; height:2.843ex;" alt="{\displaystyle w_{\max }({\mathcal {I}})}" loading="lazy"> the largest item width appearing in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> and by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)}">

</mrow>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)}</annotation>

</semantics>

</math><img src="./a68ea01f578d941530343c3a403242c38eba0675.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:25.795ex; height:5.676ex;" alt="{\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)}" loading="lazy"> the total area of these items.

Steinbergs shows that if

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }({\mathcal {I}})\leq H}</annotation>

</semantics>

</math><img src="./c8e6cd0cd81e149368d21e4dae2409dc52917a70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.094ex; height:2.843ex;" alt="{\displaystyle h_{\max }({\mathcal {I}})\leq H}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{\max }({\mathcal {I}})\leq W}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{\max }({\mathcal {I}})\leq W}</annotation>

</semantics>

</math><img src="./2f6c6ca7dd82661ac3539f4608cafdb3b583da9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.79ex; height:2.843ex;" alt="{\displaystyle w_{\max }({\mathcal {I}})\leq W}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}}">

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}}</annotation>

</semantics>

</math><img src="./81cb5e06e25a065a0a78405ed46b5da04624a6e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:56.807ex; height:2.843ex;" alt="{\displaystyle \mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a)_{+}:=\max\{0,a\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a)_{+}:=\max\{0,a\}}</annotation>

</semantics>

</math><img src="./eefb19e31f23fb8f8c2391eca6b35938120a899d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.372ex; height:2.843ex;" alt="{\displaystyle (a)_{+}:=\max\{0,a\}}" loading="lazy">,

then all the items can be placed inside the target region of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W\times H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W\times H}</annotation>

</semantics>

</math><img src="./48b5b66bfea7fa3e536659027b0a3d79d0169b40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.339ex; height:2.176ex;" alt="{\displaystyle W\times H}" loading="lazy">.

Each reduction rule will produce a smaller target area and a subset of items that have to be placed. When the condition from above holds before the procedure started, then the created subproblem will have this property as well.

Procedure 1: It can be applied if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{\max }({\mathcal {I}}')\geq W/2}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{\max }({\mathcal {I}}')\geq W/2}</annotation>

</semantics>

</math><img src="./4f27771357b644c3de0cf95919a4f26b7274f8ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.868ex; height:3.009ex;" alt="{\displaystyle w_{\max }({\mathcal {I}}')\geq W/2}" loading="lazy">.

<ol><li>Find all the items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy"> with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i)\geq W/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i)\geq W/2}</annotation>

</semantics>

</math><img src="./15c613d7c4c7d4f9d83ae5fb692691e74cf4e737.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.134ex; height:2.843ex;" alt="{\displaystyle w(i)\geq W/2}" loading="lazy"> and remove them from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">.</li>

<li>Sort them by nonincreasing width and place them left-aligned at the bottom of the target region. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{0}}</annotation>

</semantics>

</math><img src="./08c1c908b03c3f63383c7199465c7fd0b105030f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.393ex; height:2.509ex;" alt="{\displaystyle h_{0}}" loading="lazy"> be their total height.</li>

<li>Find all the items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy"> with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(i)>H-h_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(i)>H-h_{0}}</annotation>

</semantics>

</math><img src="./b5565180a2c7e98c79b98fa3630bb31be7b96fc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.346ex; height:2.843ex;" alt="{\displaystyle h(i)>H-h_{0}}" loading="lazy">. Remove them from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> and place them in a new set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}_{H}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{H}}</annotation>

</semantics>

</math><img src="./cc7956548dc9180ee532458fca035ccb6c180e13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:3.027ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{H}}" loading="lazy">.</li>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{H}}</annotation>

</semantics>

</math><img src="./cc7956548dc9180ee532458fca035ccb6c180e13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:3.027ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{H}}" loading="lazy"> is empty, define the new target region as the area above <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{0}}</annotation>

</semantics>

</math><img src="./08c1c908b03c3f63383c7199465c7fd0b105030f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.393ex; height:2.509ex;" alt="{\displaystyle h_{0}}" loading="lazy">, i.e. it has height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H-h_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H-h_{0}}</annotation>

</semantics>

</math><img src="./f1709e0d4259f94a970bb3da46bfeb09c232f8ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.297ex; height:2.509ex;" alt="{\displaystyle H-h_{0}}" loading="lazy"> and width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy">. Solve the problem consisting of this new target region and the reduced set of items with one of the procedures.</li>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}_{H}}</annotation>

</semantics>

</math><img src="./cc7956548dc9180ee532458fca035ccb6c180e13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.069ex; width:3.027ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I}}_{H}}" loading="lazy"> is not empty, sort it by nonincreasing height and place the items right allinged one by one in the upper right corner of the target area. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{0}}</annotation>

</semantics>

</math><img src="./7aa052386ec49846179aa8bbe2b279b57a675e00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.718ex; height:2.009ex;" alt="{\displaystyle w_{0}}" loading="lazy"> be the total width of these items. Define a new target area with width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W-w_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W-w_{0}}</annotation>

</semantics>

</math><img src="./c654761695d005953e1c1eaa9176cd93f576273a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.994ex; height:2.509ex;" alt="{\displaystyle W-w_{0}}" loading="lazy"> and height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H-h_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H-h_{0}}</annotation>

</semantics>

</math><img src="./f1709e0d4259f94a970bb3da46bfeb09c232f8ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.297ex; height:2.509ex;" alt="{\displaystyle H-h_{0}}" loading="lazy"> in the upper left corner. Solve the problem consisting of this new target region and the reduced set of items with one of the procedures.</li></ol>

Procedure 2: It can be applied if the following conditions hold: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}</annotation>

</semantics>

</math><img src="./390da6847e3f7645e2381931a55f0d874dabc6da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.115ex; height:2.843ex;" alt="{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}</annotation>

</semantics>

</math><img src="./f0dab602f35819fcebb6dc743781d73cb2671176.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.419ex; height:2.843ex;" alt="{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}" loading="lazy">, and there exist two different items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i,i'\in {\mathcal {I}}}">

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i,i'\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./56d35f70c75fef7d0e13f47571ce8d2c1ef9b8a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.656ex; height:2.843ex;" alt="{\displaystyle i,i'\in {\mathcal {I}}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i)\geq W/4}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i)\geq W/4}</annotation>

</semantics>

</math><img src="./7b2ba2c7da6cbdf1374bd8f500175eb12676bf1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.134ex; height:2.843ex;" alt="{\displaystyle w(i)\geq W/4}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i')\geq W/4}">

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i')\geq W/4}</annotation>

</semantics>

</math><img src="./f2913ac2d3d6d58fe2b4a44a2441679906c507bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.819ex; height:3.009ex;" alt="{\displaystyle w(i')\geq W/4}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(i)\geq H/4}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(i)\geq H/4}</annotation>

</semantics>

</math><img src="./e4d87171063c186c33f402aeb9764d7a7e9e6927.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.438ex; height:2.843ex;" alt="{\displaystyle h(i)\geq H/4}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(i')\geq H/4}">

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h(i')\geq H/4}</annotation>

</semantics>

</math><img src="./e00c2b1759520c513593247ff9f3fc7faaaed0e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.122ex; height:3.009ex;" alt="{\displaystyle h(i')\geq H/4}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H}">

</mrow>

</mrow>

<msup>

</msup>

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H}</annotation>

</semantics>

</math><img src="./99320d2cc1c212043c6f6ae711506da4a941549f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:65.725ex; height:3.009ex;" alt="{\displaystyle 2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H}" loading="lazy">.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i'}</annotation>

</semantics>

</math><img src="./c0e886069d443c081e302eade90a197e06bce427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.487ex; height:2.509ex;" alt="{\displaystyle i'}" loading="lazy"> and remove them from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">.</li>

<li>Place the wider one in the lower-left corner of the target area and the more narrow one left-aligned on the top of the first.</li>

<li>Define a new target area on the right of these both items, such that it has the width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W-\max\{w(i),w(i')\}}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W-\max\{w(i),w(i')\}}</annotation>

</semantics>

</math><img src="./1c88a0fadc8942934d97c9c713d888d32457db2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.197ex; height:3.009ex;" alt="{\displaystyle W-\max\{w(i),w(i')\}}" loading="lazy"> and height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">.</li>

<li>Place the residual items in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> into the new target area using one of the procedures.</li></ol>

Procedure 3: It can be applied if the following conditions hold: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}</annotation>

</semantics>

</math><img src="./390da6847e3f7645e2381931a55f0d874dabc6da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.115ex; height:2.843ex;" alt="{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}</annotation>

</semantics>

</math><img src="./f0dab602f35819fcebb6dc743781d73cb2671176.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.419ex; height:2.843ex;" alt="{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {I}}|>1}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {I}}|>1}</annotation>

</semantics>

</math><img src="./31111605c89bd5037cb9f97736cbb1c7765860fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.047ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {I}}|>1}" loading="lazy">, and when sorting the items by decreasing width there exist an index <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> such that when defining <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I'}}}">

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I'}}}</annotation>

</semantics>

</math><img src="./ea0a8fc899ccba2c3709731683e62394cc84606e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:2.313ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I'}}}" loading="lazy"> as the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> items it holds that

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {AREA} ({\mathcal {I}})-WH/4\leq \mathrm {AREA} ({\mathcal {I'}})\leq 3WH/8}</annotation>

</semantics>

</math><img src="./c2e1432ebfb40d08a9600016527a3adfbec8aea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:44.762ex; height:3.009ex;" alt="{\displaystyle \mathrm {AREA} ({\mathcal {I}})-WH/4\leq \mathrm {AREA} ({\mathcal {I'}})\leq 3WH/8}" loading="lazy"> as well as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i_{m+1})\leq W/4}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i_{m+1})\leq W/4}</annotation>

</semantics>

</math><img src="./9e7385a59db434ada0324a8646610d0c5abeb58e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.91ex; height:2.843ex;" alt="{\displaystyle w(i_{m+1})\leq W/4}" loading="lazy">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msup>

</msup>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{1}:=\max {W/2,2\mathrm {AREA} ({\mathcal {I'}})/H}}</annotation>

</semantics>

</math><img src="./fbfd83ac533ed8c918adcb7c402e37c6a67c7874.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.722ex; height:3.009ex;" alt="{\displaystyle W_{1}:=\max {W/2,2\mathrm {AREA} ({\mathcal {I'}})/H}}" loading="lazy">.</li>

<li>Define two new rectangular target areas one at the lower-left corner of the original one with height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> and width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{1}}</annotation>

</semantics>

</math><img src="./74ab879909bd9762251f679bbb2fa738100baa45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{1}}" loading="lazy"> and the other left of it with height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> and width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W-W_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W-W_{1}}</annotation>

</semantics>

</math><img src="./6d08caefd52729d829e061e411949262750930f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.524ex; height:2.509ex;" alt="{\displaystyle W-W_{1}}" loading="lazy">.</li>

<li>Use one of the procedures to place the items in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I'}}}">

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I'}}}</annotation>

</semantics>

</math><img src="./ea0a8fc899ccba2c3709731683e62394cc84606e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:2.313ex; height:2.509ex;" alt="{\displaystyle {\mathcal {I'}}}" loading="lazy"> into the first new target area and the items in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}\setminus {\mathcal {I'}}}">

</mrow>

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}\setminus {\mathcal {I'}}}</annotation>

</semantics>

</math><img src="./dc98d45c0b8cf4640c0258e2e30e7a52ff7946b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.069ex; width:6ex; height:3.009ex;" alt="{\displaystyle {\mathcal {I}}\setminus {\mathcal {I'}}}" loading="lazy"> into the second one.</li></ol>

Note that procedures 1 to 3 have a symmetric version when swapping the height and the width of the items and the target region.

Procedure 4: It can be applied if the following conditions hold: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}</annotation>

</semantics>

</math><img src="./390da6847e3f7645e2381931a55f0d874dabc6da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.115ex; height:2.843ex;" alt="{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}</annotation>

</semantics>

</math><img src="./f0dab602f35819fcebb6dc743781d73cb2671176.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.419ex; height:2.843ex;" alt="{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}" loading="lazy">, and there exists an item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./9d9e6bee08b6beeced9787b1df87247dc5121727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.135ex; height:2.176ex;" alt="{\displaystyle i\in {\mathcal {I}}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4}</annotation>

</semantics>

</math><img src="./134dae3a3f3e8e58b5b0a70ba4d9b7e73b61e5bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.07ex; height:2.843ex;" alt="{\displaystyle w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4}" loading="lazy">.

<ol><li>Place the item <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> in the lower-left corner of the target area and remove it from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy">.</li>

<li>Define a new target area right of this item such that it has the width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W-w(i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W-w(i)}</annotation>

</semantics>

</math><img src="./381f7996968de13f1ea64ae28b3c224d8805052a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.552ex; height:2.843ex;" alt="{\displaystyle W-w(i)}" loading="lazy"> and height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> and place the residual items inside this area using one of the procedures.</li></ol>

This algorithm has the following properties:

<ul><li>The running time can be bounded by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))}</annotation>

</semantics>

</math><img src="./075444585eb96d9d6ddf12b7c7a3c96da22ae689.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.351ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))}" loading="lazy">.<a href="#cite_note-Steinberg-8">[8]</a></li>

<li>For every set of items <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> it produces a packing of height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})}</annotation>

</semantics>

</math><img src="./bba55362d150bc3878d873203484508f2cb54ff4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.155ex; height:2.843ex;" alt="{\displaystyle ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})}" loading="lazy">.<a href="#cite_note-Steinberg-8">[8]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Pseudo-polynomial_time_approximation_algorithms">Pseudo-polynomial time approximation algorithms</h2></div>

To improve upon the lower bound of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3/2}</annotation>

</semantics>

</math><img src="./9a94d2d02968e6cbbc338b54f7762ccd20d74805.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 3/2}" loading="lazy"> for polynomial-time algorithms, pseudo-polynomial time algorithms for the strip packing problem have been considered.

When considering this type of algorithms, all the sizes of the items and the strip are given as integrals. Furthermore, the width of the strip <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"> is allowed to appear polynomially in the running time.

Note that this is no longer considered as a polynomial running time since, in the given instance, the width of the strip needs an encoding size of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log(W)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log(W)}</annotation>

</semantics>

</math><img src="./e524de84ad88a9c425aa9b36cca1ce550b06ce68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.216ex; height:2.843ex;" alt="{\displaystyle \log(W)}" loading="lazy">.

The pseudo-polynomial time algorithms that have been developed mostly use the same approach. It is shown that each optimal solution can be simplified and transformed into one that has one of a constant number of structures. The algorithm then iterates all these structures and places the items inside using linear and dynamic programming. The best ratio accomplished so far is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (5/4+\varepsilon )OPT(I)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (5/4+\varepsilon )OPT(I)}</annotation>

</semantics>

</math><img src="./eb04ffbc91faf0f2f426fe94f2731bde1b65bfdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.357ex; height:2.843ex;" alt="{\displaystyle (5/4+\varepsilon )OPT(I)}" loading="lazy">.<a href="#cite_note-JansenRau2019-20">[20]</a> while there cannot be a pseudo-polynomial time algorithm with ratio better than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 5/4}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 5/4}</annotation>

</semantics>

</math><img src="./63219705fde91ebcc4014679ab352a935bb17990.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.487ex; height:2.843ex;" alt="{\displaystyle 5/4}" loading="lazy"> unless <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=NP}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=NP}</annotation>

</semantics>

</math><img src="./04c4c7e4303f3c01c40c865c6a1a09c4632bb7e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.653ex; height:2.176ex;" alt="{\displaystyle P=NP}" loading="lazy"><a href="#cite_note-Henning-5">[5]</a>

<caption>Overview of pseudo-polynomial time approximations

</caption>

<th>Approximation Ratio</th>

<th>Source</th>

<th>Comment

</th></tr>

<tr>

<td>2010

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (3/2+\varepsilon )}</annotation>

</semantics>

</math><img src="./2e5b8d8ffbc72a509b2bc33c6db877d7d202fc83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.221ex; height:2.843ex;" alt="{\displaystyle (3/2+\varepsilon )}" loading="lazy">

</td>

<td>Jansen, Thöle<a href="#cite_note-21">[21]</a>

</td></tr>

<tr>

<td>2016

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7/5+\varepsilon )}</annotation>

</semantics>

</math><img src="./21f85b2db8a1632ff678a2f93d33ef169a47a349.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.221ex; height:2.843ex;" alt="{\displaystyle (7/5+\varepsilon )}" loading="lazy">

</td>

<td>Nadiradze, Wiese<a href="#cite_note-22">[22]</a>

</td></tr>

<tr>

<td>2016

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (4/3+\varepsilon )}</annotation>

</semantics>

</math><img src="./a8415df52dade0954a3dc7798612d18ae801231e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.221ex; height:2.843ex;" alt="{\displaystyle (4/3+\varepsilon )}" loading="lazy">

</td>

<td>Gálvez, Grandoni, Ingala, Khan<a href="#cite_note-23">[23]</a>

</td>

<td>also for 90 degree rotations

</td></tr>

<tr>

<td>2017

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (4/3+\varepsilon )}</annotation>

</semantics>

</math><img src="./a8415df52dade0954a3dc7798612d18ae801231e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.221ex; height:2.843ex;" alt="{\displaystyle (4/3+\varepsilon )}" loading="lazy">

</td>

<td>Jansen, Rau<a href="#cite_note-24">[24]</a>

</td></tr>

<tr>

<td>2019

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (5/4+\varepsilon )}</annotation>

</semantics>

</math><img src="./2db86aab24081c7d611a37b8adcf388f5f34492d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.221ex; height:2.843ex;" alt="{\displaystyle (5/4+\varepsilon )}" loading="lazy">

</td>

<td>Jansen, Rau<a href="#cite_note-JansenRau2019-20">[20]</a>

</td>

<td>also for 90 degree rotations and contiguous moldable jobs

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Online_algorithms">Online algorithms</h2></div>

In the <a href="Online_algorithm" title="Online algorithm">online variant</a> of strip packing, the items arrive over time. When an item arrives, it has to be placed immediately before the next item is known. There are two types of online algorithms that have been considered. In the first variant, it is not allowed to alter the packing once an item is placed. In the second, items may be repacked when another item arrives. This variant is called the migration model.

The quality of an online algorithm is measured by the (absolute) competitive ratio

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {sup} _{I}A(I)/OPT(I)}</annotation>

</semantics>

</math><img src="./e9b4ba90e5b8c192dbf106e7272d037c640b6613.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.585ex; height:2.843ex;" alt="{\displaystyle \mathrm {sup} _{I}A(I)/OPT(I)}" loading="lazy">,

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(I)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(I)}</annotation>

</semantics>

</math><img src="./9eab501fb1d5f3dcb70029cfad68eec486736c95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle A(I)}" loading="lazy"> corresponds to the solution generated by the online algorithm and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle OPT(I)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle OPT(I)}</annotation>

</semantics>

</math><img src="./234dc757408b781da0247c3505fc778cb4b2fe32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.136ex; height:2.843ex;" alt="{\displaystyle OPT(I)}" loading="lazy"> corresponds to the size of the optimal solution.

In addition to the absolute competitive ratio, the asymptotic competitive ratio of online algorithms has been studied. For instances <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I}</annotation>

</semantics>

</math><img src="./535ea7fc4134a31cbe2251d9d3511374bc41be9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.172ex; height:2.176ex;" alt="{\displaystyle I}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }(I)\leq 1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }(I)\leq 1}</annotation>

</semantics>

</math><img src="./e007eed64e8dc9e318804ab9a5f72fc09b0fa811.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.872ex; height:2.843ex;" alt="{\displaystyle h_{\max }(I)\leq 1}" loading="lazy"> it is defined as

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim \mathrm {sup} _{OPT(I)\rightarrow \infty }A(I)/OPT(I)}</annotation>

</semantics>

</math><img src="./4d2f78ee617298bb7a03c22de29625c3a9016783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:30.412ex; height:3.176ex;" alt="{\displaystyle \lim \mathrm {sup} _{OPT(I)\rightarrow \infty }A(I)/OPT(I)}" loading="lazy">.

Note that all the instances can be scaled such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\max }(I)\leq 1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\max }(I)\leq 1}</annotation>

</semantics>

</math><img src="./e007eed64e8dc9e318804ab9a5f72fc09b0fa811.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.872ex; height:2.843ex;" alt="{\displaystyle h_{\max }(I)\leq 1}" loading="lazy">.

<caption>Overview of online algorithms without migration

</caption>

<th>Competitive Ratio</th>

<th>Asymptotic Competitive Ratio</th>

<th>Source

</th></tr>

<tr>

<td>1983

</td>

<td>6.99

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \approx 1.7}</annotation>

</semantics>

</math><img src="./0c1714199e6cd91323c399e1e21ccefd17e9a014.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.425ex; height:2.176ex;" alt="{\displaystyle \approx 1.7}" loading="lazy">

</td>

<td>Baker and Schwarz<a href="#cite_note-BakerOnline1-25">[25]</a>

</td></tr>

<tr>

<td>1997

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1.69+\varepsilon }</annotation>

</semantics>

</math><img src="./457c70e3ed6261a3eefdef1d8856956c37f87d0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.058ex; height:2.343ex;" alt="{\displaystyle 1.69+\varepsilon }" loading="lazy">

</td>

<td>Csirik and Woeginger<a href="#cite_note-26">[26]</a>

</td></tr>

<tr>

<td>2007

</td>

<td>6.6623

</td>

<td>

</td>

<td>Hurink and Paulus<a href="#cite_note-27">[27]</a>

</td></tr>

<tr>

<td>2009

</td>

<td>6.6623

</td>

<td>

</td>

<td>Ye, Han, and Zhang<a href="#cite_note-28">[28]</a>

</td></tr>

<tr>

<td>2007

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1.58889}</annotation>

</semantics>

</math><img src="./b74a552910080be998bbd78eb5af4085e9ec0298.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.622ex; height:2.176ex;" alt="{\displaystyle 1.58889}" loading="lazy">

</td>

<td>Han et al.<a href="#cite_note-HanOnline-29">[29]</a> + Seiden<a href="#cite_note-SeidenOnline-30">[30]</a>

</td></tr></tbody></table>

The framework of Han et al.<a href="#cite_note-HanOnline-29">[29]</a> is applicable in the online setting if the online bin packing

algorithm belongs to the class Super Harmonic. Thus, Seiden's online bin packing algorithm

Harmonic++<a href="#cite_note-SeidenOnline-30">[30]</a> implies an algorithm for online strip packing with asymptotic ratio 1.58889.

<caption>Overview of lower bounds for online algorithms without migration

</caption>

<th>Competitive Ratio</th>

<th>Asymptotic Competitive Ratio</th>

<th>Source</th>

<th>Comment

</th></tr>

<tr>

<td>1982

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy">

</td>

<td>

</td>

<td>Brown, Baker, and Katseff<a href="#cite_note-31">[31]</a>

</td></tr>

<tr>

<td>2006

</td>

<td>2.25

</td>

<td>

</td>

<td>Johannes<a href="#cite_note-32">[32]</a>

</td>

<td>also holds for the parallel task scheduling problem

</td></tr>

<tr>

<td>2007

</td>

<td>2.43

</td>

<td>

</td>

<td>Hurink and Paulus<a href="#cite_note-33">[33]</a>

</td>

<td>also holds for the parallel task scheduling problem

</td></tr>

<tr>

<td>2009

</td>

<td>2.457

</td>

<td>

</td>

<td>Kern and Paulus <a href="#cite_note-34">[34]</a>

</td></tr>

<tr>

<td>2012

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1.5404}</annotation>

</semantics>

</math><img src="./5c29af80877245b1ae81016eb7b4a7fed098f08a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.459ex; height:2.176ex;" alt="{\displaystyle 1.5404}" loading="lazy">

</td>

<td>Balogh and Békési<a href="#cite_note-35">[35]</a>

</td>

<td>lower bound due to the underlying bin packing problem

</td></tr>

<tr>

<td>2016

</td>

<td>2.618

</td>

<td>

</td>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFWäscherHaußnerSchumann2007" class="citation journal cs1">Wäscher, Gerhard; Haußner, Heike; Schumann, Holger (16 December 2007). "An improved typology of cutting and packing problems". European Journal of Operational Research. 183 (3): 1109–1130. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ejor.2005.12.047">10.1016/j.ejor.2005.12.047</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0377-2217">0377-2217</a>.</cite>

</li>

<li id="cite_note-Baker1980-2">^ <a href="#cite_ref-Baker1980_2-0">a</a> <a href="#cite_ref-Baker1980_2-1">b</a> <a href="#cite_ref-Baker1980_2-2">c</a> <a href="#cite_ref-Baker1980_2-3">d</a> <a href="#cite_ref-Baker1980_2-4">e</a> <a href="#cite_ref-Baker1980_2-5">f</a> <a href="#cite_ref-Baker1980_2-6">g</a> <a href="#cite_ref-Baker1980_2-7">h</a> <a href="#cite_ref-Baker1980_2-8">i</a> <a href="#cite_ref-Baker1980_2-9">j</a> <cite id="CITEREFBakerCoffman_Jr.Rivest1980" class="citation journal cs1">Baker, Brenda S.; Coffman Jr., Edward G.; Rivest, Ronald L. (1980). "Orthogonal Packings in Two Dimensions". SIAM J. Comput. 9 (4): 846–855. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.309.8883">10.1.1.309.8883</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0209064">10.1137/0209064</a>.</cite>

</li>

<li id="cite_note-Harren-3">^ <a href="#cite_ref-Harren_3-0">a</a> <a href="#cite_ref-Harren_3-1">b</a> <cite id="CITEREFHarrenJansenPrädelvan_Stee2014" class="citation journal cs1">Harren, Rolf; Jansen, Klaus; Prädel, Lars; van Stee, Rob (February 2014). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.comgeo.2013.08.008">"A (5/3 + epsilon)-approximation for strip packing"</a>. Computational Geometry. 47 (2): 248–267. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.comgeo.2013.08.008">10.1016/j.comgeo.2013.08.008</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFNeuenfeldt_Junior" class="citation web cs1">Neuenfeldt Junior, Alvaro Luiz. <a rel="nofollow" class="external text" href="https://repositorio-aberto.up.pt/bitstream/10216/109367/2/234741.pdf">"The Two-Dimensional Rectangular Strip Packing Problem"</a> (PDF). 10820228.</cite>

</li>

<li id="cite_note-Henning-5">^ <a href="#cite_ref-Henning_5-0">a</a> <a href="#cite_ref-Henning_5-1">b</a> <cite id="CITEREFHenningJansenRauSchmarje2019" class="citation journal cs1">Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (2019). "Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing". Theory of Computing Systems. 64: 120–140. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1705.04587">1705.04587</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00224-019-09910-6">10.1007/s00224-019-09910-6</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:67168004">67168004</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFAshokKolayMeesumSaurabh2017" class="citation journal cs1">Ashok, Pradeesha; Kolay, Sudeshna; Meesum, S.M.; Saurabh, Saket (January 2017). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2016.11.034">"Parameterized complexity of Strip Packing and Minimum Volume Packing"</a>. Theoretical Computer Science. 661: 56–64. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2016.11.034">10.1016/j.tcs.2016.11.034</a>.</cite>

</li>

<li id="cite_note-MartelloExact-7">^ <a href="#cite_ref-MartelloExact_7-0">a</a> <a href="#cite_ref-MartelloExact_7-1">b</a> <a href="#cite_ref-MartelloExact_7-2">c</a> <cite id="CITEREFMartelloMonaciVigo2003" class="citation journal cs1">Martello, Silvano; Monaci, Michele; Vigo, Daniele (1 August 2003). "An Exact Approach to the Strip-Packing Problem". INFORMS Journal on Computing. 15 (3): 310–319. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fijoc.15.3.310.16082">10.1287/ijoc.15.3.310.16082</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1091-9856">1091-9856</a>.</cite>

</li>

<li id="cite_note-Steinberg-8">^ <a href="#cite_ref-Steinberg_8-0">a</a> <a href="#cite_ref-Steinberg_8-1">b</a> <a href="#cite_ref-Steinberg_8-2">c</a> <a href="#cite_ref-Steinberg_8-3">d</a> <cite id="CITEREFSteinberg1997" class="citation journal cs1">Steinberg, A. (March 1997). "A Strip-Packing Algorithm with Absolute Performance Bound 2". SIAM Journal on Computing. 26 (2): 401–409. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539793255801">10.1137/S0097539793255801</a>.</cite>

</li>

<li id="cite_note-Coffman1980-9">^ <a href="#cite_ref-Coffman1980_9-0">a</a> <a href="#cite_ref-Coffman1980_9-1">b</a> <a href="#cite_ref-Coffman1980_9-2">c</a> <a href="#cite_ref-Coffman1980_9-3">d</a> <a href="#cite_ref-Coffman1980_9-4">e</a> <a href="#cite_ref-Coffman1980_9-5">f</a> <a href="#cite_ref-Coffman1980_9-6">g</a> <a href="#cite_ref-Coffman1980_9-7">h</a> <a href="#cite_ref-Coffman1980_9-8">i</a> <a href="#cite_ref-Coffman1980_9-9">j</a> <a href="#cite_ref-Coffman1980_9-10">k</a> <cite id="CITEREFCoffman_Jr.GareyJohnsonTarjan1980" class="citation journal cs1">Coffman Jr., Edward G.; Garey, M. R.; Johnson, David S.; Tarjan, Robert Endre (1980). "Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms". SIAM J. Comput. 9 (4): 808–826. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0209062">10.1137/0209062</a>.</cite>

</li>

<li id="cite_note-Sleator-10">^ <a href="#cite_ref-Sleator_10-0">a</a> <a href="#cite_ref-Sleator_10-1">b</a> <cite id="CITEREFSleator1980" class="citation journal cs1">Sleator, Daniel Dominic (1980). "A 2.5 Times Optimal Algorithm for Packing in Two Dimensions". Inf. Process. Lett. 10: 37–40. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2880%2990121-0">10.1016/0020-0190(80)90121-0</a>.</cite>

</li>

<li id="cite_note-Golan-11">^ <a href="#cite_ref-Golan_11-0">a</a> <a href="#cite_ref-Golan_11-1">b</a> <a href="#cite_ref-Golan_11-2">c</a> <a href="#cite_ref-Golan_11-3">d</a> <a href="#cite_ref-Golan_11-4">e</a> <cite id="CITEREFGolan1981" class="citation journal cs1">Golan, Igal (August 1981). "Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms". SIAM Journal on Computing. 10 (3): 571–582. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0210042">10.1137/0210042</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFBakerBrownKatseff1981" class="citation journal cs1">Baker, Brenda S; Brown, Donna J; Katseff, Howard P (December 1981). "A 5/4 algorithm for two-dimensional packing". Journal of Algorithms. 2 (4): 348–368. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2881%2990034-1">10.1016/0196-6774(81)90034-1</a>.</cite>

</li>

<li id="cite_note-Schiermeyer-13">^ <a href="#cite_ref-Schiermeyer_13-0">a</a> <a href="#cite_ref-Schiermeyer_13-1">b</a> <a href="#cite_ref-Schiermeyer_13-2">c</a> <cite id="CITEREFSchiermeyer1994" class="citation book cs1">Schiermeyer, Ingo (1994). "Reverse-Fit: A 2-optimal algorithm for packing rectangles". Algorithms — ESA '94. Lecture Notes in Computer Science. Vol. 855. Springer Berlin Heidelberg. pp. 290–299. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbfb0049416">10.1007/bfb0049416</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-58434-6</bdi>.</cite>

</li>

<li id="cite_note-KenyonRémila-14"><a href="#cite_ref-KenyonRémila_14-0">^</a> <cite id="CITEREFKenyonRémila2000" class="citation journal cs1"><a href="Claire_Mathieu" title="Claire Mathieu">Kenyon, Claire</a>; Rémila, Eric (November 2000). "A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem". <a href="Mathematics_of_Operations_Research" title="Mathematics of Operations Research">Mathematics of Operations Research</a>. 25 (4): 645–656. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.25.4.645.12118">10.1287/moor.25.4.645.12118</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5361969">5361969</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFHarrenvan_Stee2009" class="citation book cs1">Harren, Rolf; van Stee, Rob (2009). "Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 5687. pp. 177–189. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009LNCS.5687..177H">2009LNCS.5687..177H</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-03685-9_14">10.1007/978-3-642-03685-9_14</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-03684-2</bdi>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFJansenSolis-Oba2009" class="citation journal cs1">Jansen, Klaus; Solis-Oba, Roberto (August 2009). "Rectangle packing with one-dimensional resource augmentation". Discrete Optimization. 6 (3): 310–323. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disopt.2009.04.001">10.1016/j.disopt.2009.04.001</a>.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFBougeretDutotJansenRobenek2012" class="citation journal cs1">Bougeret, Marin; Dutot, Pierre-Francois; Jansen, Klaus; Robenek, Christina; Trystram, Denis (5 April 2012). "Approximation Algorithms for Multiple Strip Packing and Scheduking Parallel Jobs in Platforms". Discrete Mathematics, Algorithms and Applications. 03 (4): 553–586. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2FS1793830911001413">10.1142/S1793830911001413</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFSviridenko2012" class="citation journal cs1">Sviridenko, Maxim (January 2012). "A note on the Kenyon–Remila strip-packing algorithm". Information Processing Letters. 112 (1–2): 10–12. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ipl.2011.10.003">10.1016/j.ipl.2011.10.003</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFHougardyZondervan2024" class="citation cs2">Hougardy, Stefan; Zondervan, Bart (2024-02-26), The Bottom-Left Algorithm for the Strip Packing Problem, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2402.16572">2402.16572</a></cite>

</li>

<li id="cite_note-JansenRau2019-20">^ <a href="#cite_ref-JansenRau2019_20-0">a</a> <a href="#cite_ref-JansenRau2019_20-1">b</a> <cite id="CITEREFJansenRau2019" class="citation book cs1">Jansen, Klaus; Rau, Malin (2019). Closing the Gap for Pseudo-Polynomial Strip Packing. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 144. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 62:1–62:14. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPIcs.ESA.2019.62">10.4230/LIPIcs.ESA.2019.62</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783959771245</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:24303167">24303167</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFJansenThöle2010" class="citation journal cs1">Jansen, Klaus; Thöle, Ralf (January 2010). "Approximation Algorithms for Scheduling Parallel Jobs". SIAM Journal on Computing. 39 (8): 3571–3615. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F080736491">10.1137/080736491</a>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFNadiradzeWiese2015" class="citation book cs1">Nadiradze, Giorgi; Wiese, Andreas (21 December 2015). "On approximating strip packing with a better ratio than 3/2". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. pp. 1491–1510. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611974331.ch102">10.1137/1.9781611974331.ch102</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-61197-433-1</bdi>.</cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFGálvezGrandoniIngalaKhan2016" class="citation book cs1">Gálvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Khan, Arindam (2016). Improved Pseudo-Polynomial-Time Approximation for Strip Packing. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 65. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 9:1–9:14. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPIcs.FSTTCS.2016.9">10.4230/LIPIcs.FSTTCS.2016.9</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783959770279</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3205478">3205478</a>.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFJansenRau2017" class="citation book cs1">Jansen, Klaus; Rau, Malin (29–31 March 2017). "Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width". WALCOM: Algorithms and Computation. Lecture Notes in Computer Science. Vol. 10167. pp. 409–420. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1610.04430">1610.04430</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-53925-6_32">10.1007/978-3-319-53925-6_32</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-53924-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15768136">15768136</a>.</cite>

</li>

<li id="cite_note-BakerOnline1-25"><a href="#cite_ref-BakerOnline1_25-0">^</a> <cite id="CITEREFBakerSchwarz1983" class="citation journal cs1">Baker, Brenda S.; Schwarz, Jerald S. (1 August 1983). "Shelf Algorithms for Two-Dimensional Packing Problems". SIAM Journal on Computing. 12 (3): 508–525. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0212033">10.1137/0212033</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFCsirikWoeginger1997" class="citation journal cs1">Csirik, János; Woeginger, Gerhard J. (28 August 1997). "Shelf algorithms for on-line strip packing". Information Processing Letters. 63 (4): 171–175. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0020-0190%2897%2900120-8">10.1016/S0020-0190(97)00120-8</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0020-0190">0020-0190</a>.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFHurinkPaulus2007" class="citation book cs1">Hurink, Johann L.; Paulus, Jacob Jan (2007). <a rel="nofollow" class="external text" href="https://ris.utwente.nl/ws/files/5327458/ParallelJobStripPacking.pdf">"Online Algorithm for Parallel Job Scheduling and Strip Packing"</a> (PDF). Approximation and Online Algorithms. Lecture Notes in Computer Science. Vol. 4927. Springer Berlin Heidelberg. pp. 67–74. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-77918-6_6">10.1007/978-3-540-77918-6_6</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-77917-9</bdi>.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFYeHanZhang2009" class="citation journal cs1">Ye, Deshi; Han, Xin; Zhang, Guochuan (1 May 2009). "A note on online strip packing". Journal of Combinatorial Optimization. 17 (4): 417–423. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10878-007-9125-x">10.1007/s10878-007-9125-x</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1573-2886">1573-2886</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:37635252">37635252</a>.</cite>

</li>

<li id="cite_note-HanOnline-29">^ <a href="#cite_ref-HanOnline_29-0">a</a> <a href="#cite_ref-HanOnline_29-1">b</a> <cite id="CITEREFHanIwamaYeZhang2007" class="citation book cs1">Han, Xin; Iwama, Kazuo; Ye, Deshi; Zhang, Guochuan (2007). "Strip Packing vs. Bin Packing". Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science. Vol. 4508. Springer Berlin Heidelberg. pp. 358–367. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0607046">cs/0607046</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-72870-2_34">10.1007/978-3-540-72870-2_34</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-72868-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:580">580</a>.</cite>

</li>

<li id="cite_note-SeidenOnline-30">^ <a href="#cite_ref-SeidenOnline_30-0">a</a> <a href="#cite_ref-SeidenOnline_30-1">b</a> <cite id="CITEREFSeiden2001" class="citation book cs1">Seiden, Steven S. (2001). "On the Online Bin Packing Problem". Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 2076. Springer Berlin Heidelberg. pp. 237–248. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-48224-5_20">10.1007/3-540-48224-5_20</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-42287-7</bdi>.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite id="CITEREFBrownBakerKatseff1982" class="citation journal cs1">Brown, Donna J.; Baker, Brenda S.; Katseff, Howard P. (1 November 1982). "Lower bounds for on-line two-dimensional packing algorithms". Acta Informatica. 18 (2): 207–225. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00264439">10.1007/BF00264439</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2142%2F74223">2142/74223</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1432-0525">1432-0525</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:21170278">21170278</a>.</cite>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFJohannes2006" class="citation journal cs1">Johannes, Berit (1 October 2006). <a rel="nofollow" class="external text" href="http://doc.rero.ch/record/318381/files/10951_2006_Article_8497.pdf">"Scheduling parallel jobs to minimize the makespan"</a> (PDF). Journal of Scheduling. 9 (5): 433–452. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10951-006-8497-6">10.1007/s10951-006-8497-6</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/20.500.11850%2F36804">20.500.11850/36804</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1099-1425">1099-1425</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18819458">18819458</a>.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite id="CITEREFHurinkPaulus2008" class="citation journal cs1">Hurink, J. L.; Paulus, J. J. (1 January 2008). <a rel="nofollow" class="external text" href="https://ris.utwente.nl/ws/files/6547720/Online_scheduling_of_parallel_jobs_on_two_machines_is_2_competitive.pdf">"Online scheduling of parallel jobs on two machines is 2-competitive"</a> (PDF). Operations Research Letters. 36 (1): 51–56. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.orl.2007.06.001">10.1016/j.orl.2007.06.001</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0167-6377">0167-6377</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15561044">15561044</a>.</cite>

</li>

<li id="cite_note-34"><a href="#cite_ref-34">^</a> <cite id="CITEREFKernPaulus2009" class="citation journal cs1">Kern, Walter; Paulus, Jacob Jan (2009). <a rel="nofollow" class="external text" href="https://research.utwente.nl/en/publications/a-note-on-the-lower-bound-for-online-strip-packing">"A note on the lower bound for online strip packing"</a>. Operations Research Letters.</cite>

</li>

<li id="cite_note-35"><a href="#cite_ref-35">^</a> <cite id="CITEREFBaloghBékésiGalambos2012" class="citation journal cs1 cs1-prop-long-vol">Balogh, János; Békési, József; Galambos, Gábor (6 July 2012). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2012.04.017">"New lower bounds for certain classes of bin packing algorithms"</a>. Theoretical Computer Science. 440–441: 1–13. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2012.04.017">10.1016/j.tcs.2012.04.017</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0304-3975">0304-3975</a>.</cite>

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> <cite id="CITEREFYuMaoXiao2016" class="citation journal cs1">Yu, Guosong; Mao, Yanling; Xiao, Jiaoliao (1 May 2016). "A new lower bound for online strip packing". European Journal of Operational Research. 250 (3): 754–759. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ejor.2015.10.012">10.1016/j.ejor.2015.10.012</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0377-2217">0377-2217</a>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-17" href="https://en.wikipedia.org/wiki/?title=Strip_packing_problem&oldid=1263496949">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>